package leetcode.code0211;

import java.util.ArrayList;
import java.util.List;

public class WordDictionary {

	class WordTreeNode {
		WordTreeNode[] branch;
		boolean isEnd;
		List<Integer> list;

		public WordTreeNode() {
			this.branch = new WordTreeNode[26];
			this.isEnd = false;
			list = new ArrayList<>();
		}

		public void addWord(char[] words) {
			int c = words[0] - 'a';
			WordTreeNode root = this.branch[c];
			if (root == null) {
				root = new WordTreeNode();
				this.branch[c] = root;
				list.add(c);
			}
			for (int i = 1; i < words.length; i++) {
				c = words[i] - 'a';
				if (root.branch[c] == null) {
					root.branch[c] = new WordTreeNode();
					root.list.add(c);
				}
				root = root.branch[c];
			}
			root.isEnd = true;
		}

		public List<Integer> branchList() {
			return list;
		}
	}

	private WordTreeNode root;

	public WordDictionary() {
		root = new WordTreeNode();
	}

	public void addWord(String word) {
		root.addWord(word.toCharArray());
	}

	public boolean search(String word) {
		return this.search(word.toCharArray());
	}

	public boolean search(char[] words) {
		List<Integer> roots = new ArrayList<>();
		int c = words[0] - 'a';
		if (words[0] == '.') {
			roots = root.branchList();
		} else {
			if (root.branch[c] == null) {// 头就不对
				return false;
			}
			roots.add(c);
		}
		for (Integer idx : roots) {
			if (this.match(words, 1, root.branch[idx]))
				return true;
		}
		return false;
	}

	private boolean match(char[] words, int index, WordTreeNode node) {
		for (int i = index; i < words.length; i++) {
			if (words[i] == '.') {
				for (Integer n : node.branchList()) {
					if (this.match(words, i + 1, node.branch[n]))
						return true;
				}
				return false;
			} else {
				int c = words[i] - 'a';
				if (node.branch[c] == null) {
					return false;
				}
				node = node.branch[c];
			}
		}
		return node.isEnd;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		WordDictionary root = new WordDictionary();
//		root.addWord("a");
//		System.out.println(root.search("a"));
//		System.out.println(root.search("."));
		root.addWord("hello");
		root.addWord("helle");
		root.addWord("he");
//		System.out.println(root);
		System.out.println(root.search("nice"));
		System.out.println(root.search("helloo"));
		System.out.println(root.search("hello"));
		System.out.println(root.search(".."));
		System.out.println(root.search("h.ll.."));
	}

}
